t,k=map(int, input().split())
mx=100003
mod=1000000007
dp=[0 for _ in range(mx)]
dp[0]=1
for i in range(1,mx):
dp[i]=dp[i-1]
if i>=k:
dp[i]+=dp[i-k]
dp[i]=dp[i]%mod
for i in range(1,mx):
dp[i]=(dp[i]+dp[i-1])%mod
for i in range(t):
a,b=map(int, input().split())
print((dp[b]-dp[a-1])%mod)
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
void solve(ll k , vector<ll>& dp , vector<ll>& dp2) {
ll ans = 0;
ll a , b;
cin >> a >> b;
// for(ll i = k ; i <= 100000 ; i++) {
// cout << dp2[i] << " ";
// }
// cout << dp2[99613] << " " << dp2[95515] << endl;
// cout << dp2[93494] - dp2[58867] << endl;
ans = (dp2[b] - dp2[a - 1])%mod;
cout << ans%mod << endl;
}
int main() {
ll t , k;
cin >> t >> k;
// t = 1;
vector<ll>dp(100001 , 1) , dp2(100001 , 0);
for(ll i = k ; i <= 100000 ; i++) {
dp[i] = (dp[i - 1] + dp[i - k])%mod;
}
for(ll i = 0 ; i <= 100000 ; i++) {
if(i == 0) {
dp2[i] = dp[i];
}
else {
dp2[i] += (dp[i] + dp2[i - 1]);
}
}
while (t--) {
solve(k , dp , dp2);
}
return 0;
}
703A - Mishka and Game | 1504C - Balance the Bits |
988A - Diverse Team | 1312B - Bogosort |
1616B - Mirror in the String | 1660C - Get an Even String |
489B - BerSU Ball | 977C - Less or Equal |
1505C - Fibonacci Words | 1660A - Vasya and Coins |
1660E - Matrix and Shifts | 1293B - JOE is on TV |
1584A - Mathematical Addition | 1660B - Vlad and Candies |
1472C - Long Jumps | 1293D - Aroma's Search |
918A - Eleven | 1237A - Balanced Rating Changes |
1616A - Integer Diversity | 1627B - Not Sitting |
1663C - Pōja Verdon | 1497A - Meximization |
1633B - Minority | 688B - Lovely Palindromes |
66B - Petya and Countryside | 1557B - Moamen and k-subarrays |
540A - Combination Lock | 1553C - Penalty |
1474E - What Is It | 1335B - Construct the String |